#include <bits/stdc++.h>
using namespace std;

/**
 * 132. 分割回文串 II
已解答
困难
相关标签
相关企业
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

 

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：

输入：s = "a"
输出：0
示例 3：

输入：s = "ab"
输出：1
 

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成
 */

// 法一
class Solution {
	public:
	int minCut(string s) {
		int n = s.size();

		// 预处理，g[i][j] 闭区间[i,j]之间是否是回文串
		bool g[n][n];
		memset(g, 1, sizeof g); // 将g全部初始化为true，都是回文串（单个字符也是回文串）

		// i左下标，j右下标
		for(int i = n - 1; i >= 0; i --){
			for(int j = i + 1; j < n; j ++){
				g[i][j] = (s[i] == s[j]) && (g[i + 1][j - 1]);
			}
		}

		int dp[n + 1]; // 闭区间[0, i]之间是否是回文串
		memset(dp, 0x3f, sizeof dp);

		// r 右端点
		for(int r = 0; r < n; r ++){
			if(g[0][r] == true){
				dp[r] = 0;
			}else{
				// j 子串的左端点
				for(int j = 0; j < r; j ++){
					if(g[j + 1][r] == true){ 
						// 如果[j+1, r] 之间是回文串，则dp[j]的分割次数 + 1（分割出[j+1, r]子串）是当前方案的次数
						dp[r] = min(dp[j] + 1, dp[r]);
					}
				}
			}
		}

		return dp[n - 1];
	}
};

// 法二
class Solution {
	public:
	int minCut(string s) {
		int n = s.size();
		if (n <= 1)
			return 0;

		// dp[i]表示从0到i的最小分割次数
		vector<int> dp(n, 0);
		// isPalindrome[i][j]表示s[i...j]是否是回文串
		vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));

		// 初始化
		for (int i = 0; i < n; ++i) {
			dp[i] = i;                 // 最坏情况下，每个字符都需要一个切割
			isPalindrome[i][i] = true; // 每个单字符子串是回文串
		}

		// 判断回文串
		for (int len = 2; len <= n; ++len) {
			for (int i = 0; i <= n - len; ++i) {
				int j = i + len - 1;
				if (s[i] == s[j]) {
					if (len == 2) {
						isPalindrome[i][j] = true;
					} else {
						isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
					}
				}
			}
		}

		// 填充dp数组
		for (int j = 1; j < n; ++j) {
			if (isPalindrome[0][j]) {
				dp[j] = 0; // 如果从0到j是回文串，不需要分割
			} else {
				for (int i = 1; i <= j; ++i) {
					if (isPalindrome[i][j]) {
						dp[j] = min(dp[j], dp[i - 1] + 1);
					}
				}
			}
		}

		return dp[n - 1];
	}
};

